// 给你一个整数数组 nums，返回 nums 中最长等差子序列的长度。
// 回想一下，nums 的子序列是一个列 nums[i1], nums[i2], ..., nums[ik] ，
// 且 0 <= i1 < i2 < ... < ik <= nums.length - 1。
// 并且如果 seq[i+1] - seq[i](0 <= i < seq.length - 1) 的值都相同，
// 那么序列 seq 是等差的。
// 来源：力扣（LeetCode）
// 链接：https://leetcode.cn/problems/longest-arithmetic-subsequence
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

/**
 * @param {number[]} nums
 * @return {number}
 */
var longestArithSeqLength = function (nums) {
  const len = nums.length
  const maxNum = Math.max(...nums)

  // dp[idx][offset] 以 nums[idx] 元素结尾的，公差为 offset 的最长子序列长度
  const dp = new Array(len).fill(0).map(() => new Array(maxNum * 2 + 1).fill(1))

  let ans = 2
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < i; j++) {
      // 这里加上 maxNum 是防止负的 offset 让数组越界
      const offset = nums[i] - nums[j] + maxNum
      dp[i][offset] = dp[j][offset] + 1
      ans = Math.max(ans, dp[i][offset])
    }
  }

  return ans
}

console.log(
  longestArithSeqLength([20, 1, 15, 3, 10, 5, 8])
)
